Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers.
Identifieur interne : 000093 ( Main/Exploration ); précédent : 000092; suivant : 000094Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers.
Auteurs : Yaron Orenstein [Israël]Source :
- Journal of computational biology : a journal of computational molecular cell biology [ 1557-8666 ] ; 2020.
Abstract
Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all k-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest k-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all k-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all k-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each k-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each k-mer either contains the k-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at mostΘ ( n log n )
DOI: 10.1089/cmb.2019.0448
PubMed: 31995404
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 000269
- to stream PubMed, to step Curation: 000269
- to stream PubMed, to step Checkpoint: 000094
- to stream Ncbi, to step Merge: 002499
- to stream Ncbi, to step Curation: 002499
- to stream Ncbi, to step Checkpoint: 002499
- to stream Main, to step Merge: 000096
- to stream Main, to step Curation: 000093
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid <i>k</i>-mers.</title><author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name><affiliation wicri:level="1"><nlm:affiliation>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva</wicri:regionArea><wicri:noRegion>Beer-Sheva</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2020">2020</date><idno type="RBID">pubmed:31995404</idno><idno type="pmid">31995404</idno><idno type="doi">10.1089/cmb.2019.0448</idno><idno type="wicri:Area/PubMed/Corpus">000269</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000269</idno><idno type="wicri:Area/PubMed/Curation">000269</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000269</idno><idno type="wicri:Area/PubMed/Checkpoint">000094</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000094</idno><idno type="wicri:Area/Ncbi/Merge">002499</idno><idno type="wicri:Area/Ncbi/Curation">002499</idno><idno type="wicri:Area/Ncbi/Checkpoint">002499</idno><idno type="wicri:Area/Main/Merge">000096</idno><idno type="wicri:Area/Main/Curation">000093</idno><idno type="wicri:Area/Main/Exploration">000093</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid <i>k</i>-mers.</title><author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name><affiliation wicri:level="1"><nlm:affiliation>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva</wicri:regionArea><wicri:noRegion>Beer-Sheva</wicri:noRegion></affiliation></author></analytic><series><title level="j">Journal of computational biology : a journal of computational molecular cell biology</title><idno type="eISSN">1557-8666</idno><imprint><date when="2020" type="published">2020</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><b>Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all <i>k</i>-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest <i>k</i>-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all <i>k</i>-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all <i>k</i>-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each <i>k</i>-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each <i>k</i>-mer either contains the <i>k</i>-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at most</b><mml:math><mml:mi>Θ</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:msqrt><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msqrt><mml:mo>log</mml:mo><mml:mi>n</mml:mi></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:math><b>characters compared with the optimum <i>n</i>. The obtained saving factor by ReverseCAKE approaches the theoretical lower bound as <i>k</i> increases. In addition, we formulated the problem as an integer linear program and empirically observed that the solutions obtained by ReverseCAKE are near-optimal. Through this work, we enable more effective design of peptide microarrays.</b></div></front></TEI><affiliations><list><country><li>Israël</li></country></list><tree><country name="Israël"><noRegion><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000093 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000093 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= pubmed:31995404
|texte= Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:31995404" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |